package com.tucc.hello.leetcode.no1_400.no1_200.no81_100.no93;

import java.util.ArrayList;
import java.util.List;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.restoreIpAddresses("25525511135"));
    }

    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        restoreIpAddresses(s, 0, new ArrayList<>(), result);
        return result;
    }

    public void restoreIpAddresses(String s, int curIndex, List<String> ip, List<String> result) {
        if (ip.size() == 4 && curIndex == s.length()) {
            result.add(String.join(".", ip));
        } else if (ip.size() < 4 && curIndex < s.length()) {
            char ch = s.charAt(curIndex);
            ip.add(s.substring(curIndex, curIndex + 1));
            restoreIpAddresses(s, curIndex + 1, ip, result);
            ip.remove(ip.size() - 1);
            if ('0' != ch) {
                if (curIndex + 1 < s.length()) {
                    char ch2 = s.charAt(curIndex + 1);
                    ip.add(s.substring(curIndex, curIndex + 2));
                    restoreIpAddresses(s, curIndex + 2, ip, result);
                    ip.remove(ip.size() - 1);
                    if (curIndex + 2 < s.length()) {
                        char ch3 = s.charAt(curIndex + 2);
                        if (ch == '1'
                                || (ch == '2' && (ch2 <= '4' || (ch2 == '5' && ch3 <= '5')))) {
                            ip.add(s.substring(curIndex, curIndex + 3));
                            restoreIpAddresses(s, curIndex + 3, ip, result);
                            ip.remove(ip.size() - 1);
                        }
                    }
                }
            }
        }
    }
}
